package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.ListNode;
import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class _112_hasPathSum {

    public List<List<Integer>> pathSum(TreeNode root) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, path, res);
        return res;

    }
    private void dfs(TreeNode node,
                    List<Integer> path,
                    List<List<Integer>> res) {
        if (node == null) {return;}
        path.add(node.val);
        if (node.left == null && node.right == null) {
            // 添加路径的时候需要 new 一个新的 ArrayList 的原因：
            // 1. 使得 res 中的对象和 path 不是同一个对象
            res.add(new ArrayList<>(path));
        }
        dfs(node.left, path, res);
        dfs(node.right, path, res);
        // 回溯的过程中，将当前的节点从 path 中删除
        path.remove(path.size() - 1);
    }


    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, path, res);
        for(List<Integer> onePath:res){
            int sum = 0;
            for(int val:onePath){
                sum+=val;
            }
            if(sum==targetSum){return true;}
        }
        return false;
    }



    //解法二
    public boolean hasPathSum1(TreeNode root, int target) {
        List<Integer> res = new ArrayList<>();
        dfs1(root, 0, res);
        for (int onePathSum : res) {
            if (onePathSum == target) {return true;}
        }
        return false;
    }

    private void dfs1(TreeNode node,int parentNodePathSum,  List<Integer> res) {
        if (node == null) {return;}
        int currNodePathSum = parentNodePathSum + node.val;
        if (node.left == null && node.right == null) {
            res.add(currNodePathSum);
        }
        dfs1(node.left, currNodePathSum, res);
        dfs1(node.right, currNodePathSum, res);
    }

    public boolean hasPathSum2(TreeNode root, int target) {
        List<Integer> res = new ArrayList<>();
        dfs2(root, target, res);
        System.out.println(res);
        for (int val : res) {
            if (val == 0) {return true;}
        }
        return false;
    }

    private void dfs2(TreeNode node, int parentNodeTarget,  List<Integer> res) {
        if (node == null) {return;}
        int currNodeTarget = parentNodeTarget - node.val;
        if (node.left == null && node.right == null) {
            res.add(currNodeTarget);
        }
        dfs2(node.left, currNodeTarget, res);
        dfs2(node.right, currNodeTarget, res);
    }


    public boolean hasPathSum3(TreeNode root, int target) {
        List<Integer> res = new ArrayList<>();
        boolean hasPathSum = dfs3(root, target, res);
        System.out.println(res);
        return hasPathSum;
    }
    private boolean dfs3(TreeNode node, int parentNodeTarget, List<Integer> res) {
        if (node == null) {return false;}

        res.add(node.val);

        int currNodeTarget = parentNodeTarget - node.val;
        if (node.left == null && node.right == null) {
            return currNodeTarget == 0;
        }
        boolean isLeftHasPathSum = dfs3(node.left, currNodeTarget, res);
        // 提前退出
        if (isLeftHasPathSum) {return true;}
        boolean isRightHasPathSum = dfs3(node.right, currNodeTarget, res);

        return isLeftHasPathSum || isRightHasPathSum;
    }
}
